package datastructure.lineralist01;


import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * 线性表操作
 *
 * @Filename: LineraListTest
 * @Author: czh
 * @Data:2023/1/3 11:40
 * 顺序表：
 * 用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况采用数组存储，
 * 在数组上完成数据的CRUD。
 * 顺序表可以分成：静态顺序表(固定长度数组)和动态顺序表(动态的数据长度)
 * 链表：
 * 是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存=存储到下一个节点的指针
 */
public class LineraListTest {
    /**
     * 静态顺序表的测试
     */
    @Test
    public void testStaticSequenceTable() {
        SequenceTable sequenceTable = new SequenceTable(20);
        for (int i = 0; i < 20; i++) {
            sequenceTable.insert(i, i);
        }
        System.out.print("遍历数组:");
        sequenceTable.display();
        System.out.print("获取数组长度:");
        System.out.println(sequenceTable.size());
        sequenceTable.insert(11);
        System.out.print("插入后的数组列表:");
        sequenceTable.display();
        sequenceTable.insert(1, 20);
        System.out.print("指定位置插入后的数组列表:");
        sequenceTable.display();
        System.out.print("插入后的获取数组长度:");
        System.out.println(sequenceTable.size());
    }

    /**
     * 链表测试
     */
    @Test
    public void testLinkNode() {
        UnidirectionalLinkedList linkedList = new UnidirectionalLinkedList();
        // 链表头加入元素
        linkedList.addHead("A");
        linkedList.addHead("B");
        //链表尾巴加入元素
        linkedList.addReal("C");
        linkedList.addReal("D");
        //[B->A->C->D]
        // 指定元素前面添加添加元素
        linkedList.addNode("A", new Node("E"));
        // 显示元素
        linkedList.display();
    }
}


/**
 * 静态和动态顺序表
 */
class SequenceTable<T> {
    /**
     * 存储的数组
     */
    public T[] elems;
    /**
     * 记录当前顺序表中的元素个数
     */
    public int num;
    /**
     * 初始容量，且不能被改变
     */
    public static final int intCapacity = 10;


    /**
     * 有参构造方法
     * 静态顺序表
     *
     * @param num
     */
    public SequenceTable(int num) {
        elems = (T[]) new Object[num];
        num = 0;
    }

    /**
     * 无参构造方法
     * 静态顺序表
     */
    public SequenceTable() {
        elems = (T[]) new Object[intCapacity];
        num = 0;
    }

    /**
     * 清空表
     */
    public void clear() {
        num = 0;
    }

    /**
     * 判断当前线性表是否为空表
     */
    public boolean isEmpty() {
        return num == 0;
    }

    /**
     * 判断当前线性表是否满
     */
    public boolean isFull() {
        if (this.elems.length == this.num) {
            return true;
        } else {
            return false;
        }
    }

    /**
     * 获取指定位置的元素
     *
     * @param i
     * @return
     */
    public T get(int i) {
        if (i < 0 || i >= num) {
            throw new RuntimeException("当前元素不存在");
        }
        return elems[i];
    }


    /**
     * 线性表插入元素
     *
     * @param t
     */
    public void insert(T t) {
        if (isFull()) {
            // 数组扩容
            this.elems = Arrays.copyOf(this.elems, 2 * this.elems.length);
        }
        elems[num++] = t;
    }

    /**
     * 在 pos 位置新增元素
     *
     * @param pos
     * @param data
     */
    public void insert(int pos, T data) {
        if (isFull()) {
            // 数组扩容
            this.elems = Arrays.copyOf(this.elems, 2 * this.elems.length);
        }
        // 插入位置后面的元素后移
        for (int i = this.num - 1; i >= pos; i--) {
            this.elems[i + 1] = this.elems[i];
        }
        this.elems[pos] = data;
        this.num++;
    }


    /**
     * 获取顺序表长度
     *
     * @return
     */
    public int size() {
        return this.num;
    }

    public void display() {
        for (int i = 0; i < this.num; i++) {
            System.out.print(this.elems[i] + " ");
        }
        System.out.println();
    }


}


/**
 * 定义单向链表类
 */
class UnidirectionalLinkedList {
    // 链表节点的个数
    public int size;
    // 头节点
    public Node head;

    // 构造器
    public UnidirectionalLinkedList() {
        size = 0;
        head = null;
    }

    /**
     * 在链表头添加元素
     *
     * @param obj
     * @return 返回插入的数据
     */
    public Object addHead(Object obj) {
        Node newNode = new Node(obj);
        if (size == 0) {
            head = newNode;
        } else {
            newNode.next = head;
            head = newNode;
        }
        size++;
        return obj;
    }

    /**
     * 在链表尾添加元素
     *
     * @param obj
     * @return 返回插入的数据
     */
    public Object addReal(Object obj) {
        Node newNode = new Node(obj);
        if (size == 0) {
            head = newNode;
            size++;
            return obj;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
        size++;
        return obj;
    }

    /**
     * 在指定元素前面添加元素
     *
     * @param obj
     * @return 返回插入的数据
     */
    public void addNode(Object obj, Node newNode) {
        Node current = head;
        Node pre = head;
        int tempSize = size;
        while (tempSize > 0) {
            if (current.data.equals(obj)) {
                // 在表尾插入
                if (current.next == null) {
                    current.next = newNode;
                }
                // 在表头插入
                else if (current == head) {
                    newNode.next = head;
                    head = newNode;
                } else {
                    // 表中插入
                    newNode.next = current;
                    pre.next = newNode;
                }
                size++;
                break;
            } else {
                pre = current;
                current = current.next;
            }
            tempSize--;
        }
    }

    /**
     * 删除链表头数据
     *
     * @return 返回删除的数据
     */
    public Object deleteHead() {
        if (size == 0) {
            throw new RuntimeException("链表中不存在元素");
        } else {
            Object data = head.data;
            head = head.next;
            size--;
            return data;
        }
    }

    /**
     * 查找指定元素，找到了返回节点Node，找不到返回null
     *
     * @param obj
     * @return
     */
    public Node find(Object obj) {
        Node current = head;
        int tempSize = size;
        while (tempSize > 0) {
            if (current.data.equals(obj)) {
                return current;
            } else {
                current = current.next;
            }
            tempSize--;
        }
        return null;
    }

    /**
     * 删除指定的元素，删除成功返回true
     *
     * @param obj
     * @return
     */
    public boolean delete(Object obj) {
        if (size == 0) {
            return false;
        }
        Node current = head;
        Node previous = head;
        while (!current.data.equals(obj)) {
            if (current.next == null) {
                return false;
            } else {
                previous = current;
                current = current.next;
            }
        }
        // 如果要删除的是第一个节点
        if (current == head) {
            head = current.next;
            size--;
        } else {
            previous.next = current.next;
            size--;
        }
        return true;
    }

    /**
     * 判断链表是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 显示节点信息
     */
    public void display() {
        if (size > 0) {
            Node node = head;
            int tempSize = size;
            if (tempSize == 1) {
                System.out.println(node.data);
                return;
            }
            while (tempSize > 0) {
                if (node.equals(head)) {
                    System.out.print("[" + node.data + "->");
                } else if (node.next == null) {
                    System.out.print(node.data + "]");
                } else {
                    System.out.print(node.data + "->");
                }
                node = node.next;
                tempSize--;
            }
            System.out.println();
        } else {
            System.out.println("链表为空");
        }
    }
}

// 链表的节点类
class Node {
    // 每个节点的数据
    public Object data;
    // 每个节点指向下一个节点的连接
    public Node next; // 指向下一个节点

    // 构造器
    public Node(Object data) {
        this.data = data;
    }
}

